#pragma once

#include "iostream"
#include "vector"
#include "algorithm"
#include <numeric>

using namespace std;

/*HJJ QQ479287006
 *给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。

算法的时间复杂度应该为 O(log (m+n)) 。

 

示例 1：

输入：nums1 = [1,3], nums2 = [2]
输出：2.00000
解释：合并数组 = [1,2,3] ，中位数 2
示例 2：

输入：nums1 = [1,2], nums2 = [3,4]
输出：2.50000
解释：合并数组 = [1,2,3,4] ，中位数 (2 + 3) / 2 = 2.5

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/median-of-two-sorted-arrays
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * */

//因为这个通过是 开辟了空间了 而且还是O（n）
double findMedianSortedArrays(vector<int> &nums1, vector<int> &nums2) {
    vector<double> nums3;
    int low1 = 0, low2 = 0;
    while (low1 < nums1.size() && low2 < nums2.size()) {
        if (nums1[low1] <= nums2[low2])
            nums3.push_back(nums1[low1++]);
        else
            nums3.push_back(nums2[low2++]);
    }

    while (low2 < nums2.size())
        nums3.push_back(nums2[low2++]);
    while (low1 < nums1.size())
        nums3.push_back(nums1[low1++]);

    int le = nums3.size() / 2;
    //如果是偶数
    if (nums3.size() % 2 == 0)
        return (nums3[le] + nums3[le - 1]) / 2;
    return nums3[le];
}


int partition(vector<int> &numsSum, int low, int high) {
    int p = numsSum[low];//应该是low不应该是0
    while (low < high) {
        //注意不能有等于号
        while (low < high && numsSum[high] >= p) --high;    //将比枢轴记录小的记录移到低端
        numsSum[low] = numsSum[high];
        while (low < high && numsSum[low] <= p) ++low;
        numsSum[high] = numsSum[low];       //将比枢轴记录大的记录移到高端
    }
    numsSum[low] = p;          //枢轴记录到位
    return low;                 //返回枢轴位置

}

//递归方法寻找
int getTopKRe(vector<int> &numsSum, int low, int high, int index) {
    int mid = partition(numsSum, low, high);
    if (mid == index) return numsSum[mid];//如果是返回那个数
    if (index > mid) return getTopKRe(numsSum, mid + 1, high, index);
    if (index < mid) return getTopKRe(numsSum, low, mid - 1, index);
    return -1;
}

//递归方法寻找
//int getTopKRe2(vector<int>& nums1,vector<int>& nums2,int low ,int high,int index)
//{
//    // 假如长度为nums1+nums2 num1属于 0到k num2 属于 k+1 到knum2.size
//
//    int mid= partition(nums1, low, high);
//    if (mid>=nums1.size() && mid==index)
//    {
//        return nums2[mid]; //如果是返回那个数
//    }
//    if (mid<nums1.size() && mid==index)
//    {
//        return nums1[mid]; //如果是返回那个数
//    }
//
//    if(index>mid && mid<nums1.size() )
//    {
//        return getTopKRe(numsSum,mid+1,high,index);
//    }
//
//    //if (mid==index) return numsSum[mid];//如果是返回那个数
//    if (index>mid) return getTopKRe(numsSum,mid+1,high,index);
//    if (index<mid) return getTopKRe(numsSum,low,mid-1,index);
//    return -1;
//}
int getTopK(vector<int> &numsSum, int low, int high, int index) {
    while (true) {
        int mid = partition(numsSum, low, high);
        if (index > mid) {
            low = mid + 1;
        } else if (index < mid) {
            high = mid - 1;
        } else {
            return numsSum[mid];
        }

    }
}

//第二种更慢 还有别的topk方法吗
//我们分别找第 (m+n+1) / 2 个，和 (m+n+2) / 2 个，然后求其平均值即可，这对奇偶数均适用
double findMedianSortedArrays2(vector<int> &nums1, vector<int> &nums2) {
    vector<int> sumNum;
//    for (const auto &item : nums1)
//        sumNum.push_back(item);
//    for (const auto &item : nums2)
//        sumNum.push_back(item);

    sumNum.insert(sumNum.end(), nums1.begin(), nums1.end());
    sumNum.insert(sumNum.end(), nums2.begin(), nums2.end());

// 可以使用快排求topK的方式 寻找 (m+n+1) / 2    (m+n+2) / 2
    int le = sumNum.size() / 2;
    //如果是偶数
    double leVal = getTopK(sumNum, 0, sumNum.size() - 1, le);
    double leDes1Val = getTopK(sumNum, 0, sumNum.size() - 1, le - 1);

    if (sumNum.size() % 2 == 0) {
        return (leVal + leDes1Val) / 2;
    }


    return leVal;


}

/**
 *这个思想没问题 需要再理解
 *     vector<int> sum={ 9, 8, 4, 3215, 1, 54, 9, 3 };
    vector<int> vector1={1,2,3,5,6}; // [ 5 6]     k=4   //从0开始 k=3  k=2  k=0
    vector<int> vector2={3,4,7,8}; //   [4,7,8]
    // 1 2 3 3 4 5 6 7 8
 * */

//网上抄的
// int getKthElement(int[] nums1, int[] nums2, int k) {
//    /* 主要思路：要找到第 k (k>1) 小的元素,那么就取 pivot1 = nums1[k/2-1] 和 pivot2 = nums2[k/2-1] 进行比较
//    * 这里的 "/" 表示整除
//    * nums1 中小于等于 pivot1 的元素有 nums1[0 .. k/2-2] 共计 k/2-1 个
//    * nums2 中小于等于 pivot2 的元素有 nums2[0 .. k/2-2] 共计 k/2-1 个
//    * 取 pivot = min(pivot1, pivot2),两个数组中小于等于 pivot 的元素共计不会超过 (k/2-1) + (k/2-1) <= k-2 个
//    * 这样 pivot 本身最大也只能是第k-1小的元素
//    * 如果 pivot = pivot1,那么 nums1[0 .. k/2-1] 都不可能是第 k 小的元素。把这些元素全部 "删除",剩下的作为新的 nums1 数组
//    * 如果 pivot = pivot2,那么 nums2[0 .. k/2-1] 都不可能是第 k 小的元素。把这些元素全部 "删除",剩下的作为新的 nums2 数组
//    * 由于我们 "删除" 了一些元素（这些元素都比第 k 小的元素要小）,因此需要修改 k 的值,减去删除的数的个数
//    */
//
//    int length1 = nums1.length, length2 = nums2.length;
//    int index1 = 0, index2 = 0;
//    int kthElement = 0;
//
//    while (true) {
//        // 特殊情况
//        if (index1 == length1) {  // 第二种特殊情况,一个数组为空
//            return nums2[index2 + k - 1];
//        }
//        if (index2 == length2) {  // 第二种特殊情况,一个数组为空
//            return nums1[index1 + k - 1];
//        }
//        if (k == 1) {             // 第三种特殊情况,k=1
//            return Math.min(nums1[index1], nums2[index2]);
//        }
//
//        // 正常情况,index1,index2作为起始点,newindex1,newindex2作为比较点 在不停的更新
//        int half = k / 2;
//        int newIndex1 = Math.min(index1 + half, length1) - 1; //第一种特殊情况,发生越界,记录需要比较的位置
//        int newIndex2 = Math.min(index2 + half, length2) - 1;  //第一种特殊情况,发生越界,记录需要比较的位置
//        int pivot1 = nums1[newIndex1], pivot2 = nums2[newIndex2];  //获取两个需要比较的数
//        if (pivot1 <= pivot2) {  // <=将两种情况合并
//            k -= (newIndex1 - index1 + 1); //两者相减后+1,这才是真正减去的长度
//            index1 = newIndex1 + 1;  //连同比较位置也一同删去了,所以新的开始是 比较位置 的后一位
//        } else {
//            k -= (newIndex2 - index2 + 1);
//            index2 = newIndex2 + 1;
//        }
//    }
//}
